Nota: Cuando nos presentan un razonamiento hay dos tipos de razonamientos categoricos y no categoricos. En los categoricos las premisas tienen cuantificadores (∀x:,∃x:) y por lo tanto definir un conjunto universal e.g: U={x/“x es un auto”}, las premisas son funciones e.g: p(x)=“x es verde”, por ultimo, en el caso de que un razonamiento categorico sea invalido la forma de justificar que es invalido es definiendo un conjuto que demuestre la contradiccion del argumento.
Caso contrario son los no categoricos, en este caso las premisas no tienen cuantificadores, tampoco hay que definir un conjunto universal.
Reglas de Inferencia
Nombre
Condiciones
Modus Ponens "M.P."
A⇒B;A∴B
Modus Tolens "M.T."
A⇒B;¬B∴A
Silogismo Hipotetico "S.H."
A⇒B;B⇒C∴A⇒C
Silogismo Disyuntivo "S.D."
A∨B;¬A∴B
Ley de Combinacion "L.C."
A;B∴A∧B
Reglas de Inferecia Razonamientos Categoricos (CON CUANTIFICADORES):
Nombre
Condiciones
Particularizacion Universal "P.U."
∀x:p(x)∴p(a)
Generalizacion Universal "G.U."
p(a)∴∀x:p(x)(Solo se cumple si “a" es generico)
Particularizacion Existencial "P.E."
∃x:p(x)∴p(a)
Generalizacion Existencial "G.E."
p(a)∴∃x:p(x)
p⇒q{¬q⇒¬p
Unidad 2.1: Conjuntos
Propiedades de la inclusion
X⊆Y⇔∀a:a∈X⇒a∈Y
∀A:A⊆A. Todo conjunto esta incluido en si mismo.
∀A:∅⊆A. El vacio esta incluido en todo conjuto.
∀A:A⊆U. Todo conjunto esta includo en el Universal.
∀A,B,C:A⊆B∧B⊆C⇒A⊆C. Propiedad Transitiva.
Operaciones entre conjuntos
Operacion
Formula
Union
A∪B=x/x∈A∨x∈B
Interseccion
A∩B=x/x∈A∧x∈B
Diferencia
A−B=A∩¬B=x/x∈A∧x∈/B
Complemento
¬A=U−A
Diferencia Simetrica
AΔB=x/x∈A⊻x∈B
Propiedades de las Operaciones
#
Nombre
Propiedad
1
Involucion
¬(¬A)=A
2
Conmutativida
A∪B=B∪AA∩B=B∩A
3
Asociatividad
A∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩C
4
Distributividad
A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)
5
Idempotencia
A∪A=AA∩A=A
6
Leyes de Morgan
¬(A∩B)=¬A∪¬B ¬(A∪B)=¬A∩¬B
7
Neutro
A∩U=AA∪∅=A
8
Absorbente
A∩∅=∅ A∪U=U
9
Absorcion
A∩(A∪B)=AA∪(A∩B)=A
10
Equivalencia de la Diferencia
A−B=A∩¬B
11
Complementacion
A∩¬A=∅ A∪¬A=U
hola
Conjunto de Partes
P(A)=X/X⊆A
X∈P(A)⇔X⊆A
Definicion: Dado un conjuto A, se define como conjuto de Partes de A al conjunto formado por todos los subconjuntos de A. Se denota como P(A), e.g: A=1,2P(A)=∅,{1},{2},A.
ACLARACIONES:
∣P(A)∣=2∣A∣
P(∅)=∅(20=1∴∣P(∅)∣=1)
Particion de un conjunto
Definicion: Sea un cojunto A=∅. Sea P=A1,A2,A3,…,An, P es una particion si:
Ai=∅∀i
Ai∩Aj=∅∀i=j
∪Ai=A
continuara?...
Producto Cartesiano
Definicion: Dados dos conjuntos A y B, llamamos producto cartesiano de A por B al conjunto:
A×B=(x;y)/x∈A∧x∈B
El producto cartesiano esta formado por pares ordenados.
Justamente como son pares ordenados, no es conmutativa, es decir, A×B=B×A,porque (x;y)=(y;x).
Propiedades del producto cartesiano
#
Propiedad
1
A×∅=∅×A=∅
2
A×B=B×
3
A×(B×C)=(A×B)×A
4
(A∩B)×C=(A×C)∩(B×C)(A∪B)×C=(A×C)∪(B×C)
Demostraciones
En un caso de demostracion se compone de la siguiente manera, se tiene una o varias hipotesis y una sola tesis, LAS HIPOTESIS SE CONSIDERAN CIERTAS, y es gracias a esto que vamos a poder reemplazar alguna expresion de la tesis por una de la hipotesis
Caso particular: Si tengo que demostrar una igualdad ( = ) debo hacer la demostracion en ambos sentidos, es decir, partir desde el miembro izquierdo, desarrollar hasta llegar al derecho y viceversa. EN ALGUNOS CASOS, las propiedades se pueden aplicar en ambos sentidos, pero esto no siempre se cumple, para esos casos solo queda volver a empezar el desarrollo desde cero.
Demostraciones con Partes de Conjuntos
Cuando se tiene que demostrar algo que involucre partes de un conjunto, se trabaja de la misma manera que con conjuntos, solo que ahora los elementos de P(A) (siendo A un conjunto o subconjunto generico) van a ser otros conjuntos. Esto es poruqe P(A) nos devuelve otro conjunto... pero de mas conjuntos.
En vez de representar un elemento del conjunto como ∀x:x∈A sera de esta forma ∀X:X∈A. Notese la diferencia que ahora el elemento generico del conjunto es otro conjunto.
Ademas, a la hora de reemplazar partes de un conjunto, se habla de un conjunto generico que esta incluido en este supuesto conjunto.
E.g: P(A)⇒∀X:X∈P(A)⇒X⊆A
El resto de la demostracion deberia ser identica que con conjuntos.
Unidad 2.2: Induccion
PIC (Principio de Induccion Completa)
v[p(1)]=V Paso base.
v[p(h)]=V⇒v[p(h+1)]=V Paso inductivo.
Aclaraciones:
Paso Base: En el paso base lo que se busca es demostrar que la proposicion es verdadera evaluada en 1, si este no cumple con el paso base entonces la proposicion es falsa.
Paso Inductivo: El paso inductivo es el planteo de un condicional, si cumple con un elemento generico "h" entonces cumplira con el siguiente a ese elemento inductivo "h+1".
Este condicional se divide en dos partes, antecedente y consecuente, pero en este caso lo llamaremos hipotesis inductiva al antecedente y tesis inductiva al consecuente.
La induccion solo aplica a proposiciones que trabajen en el conjunto de los elementos naturales.
En ejercicios de divisiblilidad quiza convenga descomponer algun numero en la suma o resta de dos numeros, la idea es que alguno de estos dos sea multiplo del numero que se busca
Puede llegar a suceder que en algn caso tenga que evaluar si h es impar o par, para evaluar si se puede hacer un factor comun o algo del estilo hasta llegar al multiplo que se busca.
Si se tiene una suma de potencias lo mejor es tratar de descomponer la suma del exponente (si es que hay).
En ejercicios de inecuaciones es bastante complicado poder desarrollar el ejercicio, lo que se recomienda es usar la logica y reemplazar por valores relacionados de alguna forma con la hipotesis.
en general estos tienen una limitacion para n por ejemplo n≥5 en este caso se sabe que n tiene que ser mayor o igual que 5, esto nos sirve para reemplazarlo en alguna expresion.
En casos raros puede que tengas que reemplazar un termino por otro completamente distinto, mientras que se mantenga la desigualdad, vale. Recordar que siempre el objetivo es llegar a una expresion relacionada con nuestra tesis.
En ejercicios de sumatoria es necesario "sacarnos" la sumatoria de en medio, para esto podemos descomponer la sumatoria en una suma de la sumatoria y otra expresion.
hola
hola
holahola
Unidad 3: Divisibilidad
Se trabaja en el conjunto Z
Division entera
Dados dos numeros D y d, con d=0, existen y son unicos otros dos enteros c y r tales que:
D=c⋅d+r y 0≤r≤∣d∣
En divisiones de Dividendo negativo es provable que al cociente le tenga que sumar 1 al numero que usaria de costubre porque el resto no puede ser negativo.
Si d>0:
c=ent(dD)∧r=mant(dD)⋅d
Si d<0:
d′=−d⇒c′=ent(d′D)∧r′=mant(d′D)
Luego:
c=c′∧r=r′
Si el divisor el negativo entonces lo que se debe hacer es
Cambiar el signo al divisor (osea ahora es positivo)+
Obtener el cociente y resto
Cambiar de signo al cociente, el resto queda igual
Si el cociente es resultado de D/d es negativo el cociente se trunca hacia ariba, osea si es -39.78 el cociente sera -40
De lo contrario si el resultado de D/d el cociente se trunca hacia abajo ⌊
Numeros Primos: Son los numeros enteros positivso mayores que 1, que solo son divisibles por 1,−1,n,−n
Propiedad:
Sean, p,a,b∈Z: Si n∣a⋅b∧p:primo⇒n∣a∨n∣b
Teorema Fundamental de la Aritmetica
Todo numero entero es o bien primo o se puede escribir como producto de factores primos de manera unica salvo el orden
n=p1k1⋅p2k2⋅…⋅prkr
Esto es la wea de factorear...
Minimo comun Multiplo (M.C.M)
Proceso para obtener el m.c.m de cualquier numero:
Descomponer los numeros en sus factores primos.
Buscar todos los factores que aparezcan y si hay repetidos quedarse con el de mayor exponete.
hola
hola
Maximo comun Divisor (M.C.D)
Proceso para obtener el m.c.d de cualquier numero:
Descomponer los numeros en sus factores primos.
Buscar los factores en comun y quedarse con el factor de menor exponente.
Propiedad:
mcm(a,b)⋅mcd(a,b)=∣a⋅b∣
d=mcd(a,b)⇒d=s⋅a+t⋅b con s,t∈Z
Algoritmmo de Euclides
El algoritmo de euclides se usa para calcular el maximo comun divisor (mcd) entre dos numeros, pero ademas se utiliza para expresarlos como combinacion lineal.
Propiedad:
Dados dos enteros a y b, el mcd(a,b)=mcd(b,r) siendo r el resto de la division de a por b.
Se dividen los numeros (el mas chico divide al mas grande)
Se obtiene el cociente y el resto
Luego el resto divide al divisor previo
Se repite el proceso hasta que el resto valga 0.
EL resto llega a 0 el resto prevo sera el mcd entre los dos numeros.
Algoritmo de Euclides de Forma Matricial
Siendo: mcd(a,b)=n
n=k1⋅a+k2⋅b
Ej: Calcular mcd (720,224)
hola
hola
hola
hola
hola
#
k1
k2
n
Operacion de Filas
1
1
0
720
F1
2
0
1
224
F2
3
1
−3
48
F3=F1−3⋅F2
4
−4
13
32
F4=F2−4⋅F3
5
5
−16
16
F5=F3−F4
6
0
F6=F4−2⋅F5
Ahora tomo la anteultima fila, en ella estaran los valores que necesito:
mcd$(720,224) = 16$
16=5⋅720+(−16)⋅224
A la hora de completar la matriz trabajar siempre con valores positivos para evitar errores, pero si se cambia de signo algun numero recordar cambiarle el signo tambien al numero que multiplique a dicho numero que se cambio el signo.
Teorema de Bezout
Dados dos enteros a y b:
mcd(a,b)=1⟺1=s⋅a+t⋅b con s,t∈Z
Esto solo sucede si y solo si el mcd$(a,b) = 1$.
Dos numeros son coprimos si el mcd$(a,b)=1$
Dos numeros son coprimos si s combinacion lineal da 1
Por el teorema de Bezout dos numeros consecutivos siempre son coprimos
Algunas recomendaciones
TENER MUY EN CUENTA QUE SE ESTA TRABAJANDO EN Z, POR LO TANTO LOS NUMEROS NEGATIVOS TAMBIEN CUENTAN.
En ejercicios de divisibilidad van a expresar una division con palabras. El primer paso es entenderla, luego nos van a dar otra division distinta, pero que hace uso de la primera. La clave esta en tratar de expresar toda esta nueva expresio como una division del caracter que nos estan pidiendo.
Este al ser un bicondicional se cumple en ambos sentidos, es decir si cumple con mcd = 1 tambie cumple con la combinacion lineal.
Si el mcd entre dos numeros me da un numero d este se puede expresar como combinacion lineal, pero si una combinacion lineal da un numero d, este no necesariamente es el mcd entre dos numeros.
Como obtener todos los divisores de un numero:
Descomponer a un numero en sus factores primos
Para saber cuantos divisores son, a cada exponente se le suma 1 y despues se multiplican entre si. Eso da la cantidad de divisores.
Luego armar la cuadricula con todas las combinaciones
Unidad 4: Relaciones
Definiciones
Dados dos conjuntos A y B, llamamos relacion de A en B a cualquier subconjunto de A×B
R:A→BR es una relacion de A en B. (R⊆A×B) es cualquier subconjunto incluido en el producto cartesiano.
R al ser un conjunto se puede representar igual que los conjuntos:
Por extension
Por Diagrama de Venn
Tablas
Graficos cartesianos (son diagramas de ejes con un punto en donde hay una relacion)
Para que una funcion sea biyectiva los cardinales del conjunto de partida como el de llegada deben ser iguales.
Operaciones entre Matrices
Suma Logica o Disyuncion (∨):
A∨B=C Donde A∈{0,1}n×m,B∈{0,1}n×m,C∈{0,1}n×m.
∀i:1…n:∀j:1…m:cij=aij∨bij
Producto Logico o Conjunsion (∧):
A∧B=C Donde A∈{0,1}n×m,B∈{0,1}n×m,C∈{0,1}n×m.
∀i:1…n:∀j:1…m:cij=aij∧bij
Producto Matricial Booleano (∙):
A⋅B=C Donde A∈{0,1}n×m,B∈{0,1}m×p,C∈{0,1}n×p.
At=B Donde A∈{0,1}n×m,B∈{0,1}n×m.
∀i:1…n:∀j:1…m:bij=aji
Complemento de una matriz:
Aˉ=B Donde A∈{0,1}n×m,B∈{0,1}n×m.
∀i:1…n:∀j:1…m:bij=¬aij
Propiedades de Matrices
#
Nombre
Propiedad
1
Idempotencia
A∨A=A, A∧A=A
2
Conmutatividad
A∨B=B∨AA∧B=B∧A
3
Asociatividad
A∨(B∨C)=(A∨B)∨CA∧(B∧C)=(A∧B)∧CA⋅(B⋅C)=(A⋅B)⋅C
4
Asociatividad
A∨A=A, A∧A=A
5
Distributividad
A∨(B∧C)=(A∨B)∧(A∨C)A∧(B∨C)=(A∧B)∨(A∧C)
Comparacion de Matrices
Sean A,B∈{0,1}n×m
A<B⇔aij<bij∀i,∀j
A≤B⇔aij≤bij∀i,∀j
En una matriz que es menor o igual que otra lo unico que importa es que en la matriz que es menor si tiene un 1, es necesario que en la otra tambien haya un 1
Matriz de una Relacion
Sea R:A→B con A={a1,a2,…,an} y B={b1,b2,…,bn}
MR∈{0,1}n×m{10 si (ai,bj)∈R si (ai,bj)∈/R
Operaciones con Matrices
Sean R:A→B y S:A→B
Sea MR la matriz de R y MS la matriz de S
MR∪S=MR∨MSMR∩S=MR∧MSMR−1=(MR)tMR=(MR)
Composicion de Relaciones
Dadas R:A→B y S:B→C
S∘R={(x,z)∈A×C/∃y∈B∧(x,y)∈R∧(y,z)∈S}
Para hacer composicion de matrices hay que hacer el producto matricial entre las matrices, el resultado sera la matriz de la relacion compuesta. Se tiene que respetar el orden.
MS∘R=MR⋅MS
Relaciones Binarias
Son todas las relaciones que conjunto de partida es igual al de llegada R:A→A.
Ej: R:A→A tal que R={(x,y)∈A×A/y=x2}
hola
hola
hola
hola
hola
hola
hola
hola
hola
Propiedades de las Relaciones
Sea una relacion binaria R:A→A:
R es Reflexiva⇔∀a∈A:(a,a)∈R
En un diagrama de Venn tiene que haber bucles en todos los elementos
En forma matricial la diagonal principal tiene que estar llena de 1.
I≤M(R)
R es A-Reflexiva⇔∀a∈A:(a,a)∈/R
En un diagrama de Venn NO tiene que haber bucles en todos los elementos.
En forma matricial la diagonal principal tiene que estar llena de 0.
I∧M(R)=N
R es Simetrica⇔∀a,b∈A:(a,b)∈R⇒(b,a)∈R
En un diagrama de Venn si un elemento se relaciona con otro, este tanbien se debe relacionar con el primero.
Todos los 1 que esten de un lado de la diagonal principal, tambien deben estar del otro.
M(R)=M(R)t.
R es Asimetrica⇔∀a,b∈A:(a,b)∈R⇒(b,a)∈/R
En un diagrama de Venn si un elemento se relaciona con otro, este NO SE debe relacionar con el primero. Osea ni bucles ni caminos de ida y vuelta.
Todos los 1 que esten de un lado de la diagonal principal, NO deben estar del otro.
M(R)∧M(R)t=N.
R es Antisimetrica⇔∀a,b∈A:(a,b)∈R∧(b,a)∈R⇒a=b
En un diagrama de Venn si un elemento se relaciona con otro, este NO SE debe relacionar con el primero. En este caso si hay bucles pero no caminos de ida y vuelta.
Todos los 1 que esten de un lado de la diagonal principal, NO deben estar del otro, a exepcion de la diagonal principal.
M(R)∧M(R)t≤I.
R es Transitiva⇔∀a,b,c∈A:(a,b)∈R∧(b,c)∈R⇒(a,c)∈R
En un diagrama de Venn si dos elementos (o mas) estan relacionados, entonces tienen que estar todas las relaciones posibles.
La una forma de verificar esta propiedad es haciendo el producto matricial y verificar que los unos que esten en el resultado esten en la matriz original (lo que dice la propiedad).
M(R)⋅M(R)≤M(R).
A transitiva es lo opuesto a la transitivia
Orden de evaluacion
Es reflexiva?
Es a-reflexiva?
Es simetrica?
Es a-simetrica?
Es antisimetrica?
Es transitiva?
Nota: Cuando son elementos finitos lo mejor es realizar la matriz, pero cuando son elementos infinitos tendremos que recurrir a la defincion.
Relacion de Conectividad
Sea R:A→AR2=R∘R
En R:x→y→zEn R2=x→z
En otras palabras la matris de R2 nos devuelve todas las relaciones cuyos caminos son de longitud 2.
Esto tambien sucede para cualquier potencia n, nos devuelve todos los caminos de longitud n.
xRny⇔exite un camino de longitud n entre x e y
Relacion de Equivalencia
R:A→A es de quivalencia si es⎩⎨⎧ReflexivaSimetricaTransitiva
A las relaciones de quivalencia se las suele representar por el simbolo ~
Clase de Equivalencia
Sea (A;~)a=[a]=Cl(a)={x∈A/x~a}
Conjunto de Clases
Sea (A;~)A/~={Cl(a)/a∈A}
Propiedades de las Clases de Equivalencia
Aclaracion 1: Las siguientes propiedades son validas porque se parte de que es una relacion de equivalencia, es decir, ya esta demostrado que la relacion es de equivalencia.
Aclaracion 2: Es lo mismo decir Cl(a) que [a]
Consideremos R relacion de equivalencia definida en un conjunto A
Proiedad 1:∀a∈A:[a]=∅
Dem: Como se cumple la propiedad reflexiva de R en A: ∀a∈A:aRa⇒a∈[a]⇒[a]=∅
Propiedad 2:Si a∈[b]⇒b∈[a]
Dem: Si a∈[b]⇒aRb (por def. de clase de Eq.)⇒bRa (por la prop. simetrica)⇒b∈[a] (por def. de clase de Eq.)
Propiedad 3: Las clases de equivalencia son disjuntas "Dos a dos."
Basicamente que las clase no se intersectan, y si lo hacen deben ser identicas
Teorema Fundamental de las Relaciones de Equivalencia
Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"
Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.
Relacion de Equivalencia⟺Particion del conjunto
Basicamente cada relacion de equivalencia me determina una particion del conjunto (recordar definicion de particion). Y si hay una particion dentro del conjunto es porque hay una relacion de equivalencia que lo determina.
Demostracion del teorema
Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"
Propiedades que debe cumplir:
Cl(x)=∅
Cl(x)∩Cl(y)=∅(si Cl(x)=Cl(y))
∪Cl(x)=A
Dem: ∀x∈A:x∈Cl(x) por reflexividad⇒x∈∪Cl(x)
Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.
Por hipotesis P={A1,A2,A3,…,An} es una particion de A.
Deinimos en A:xRy⇔∃Ai∈P:x∈Ai∧y∈Aj)
Reflexiva: ∀x∈A:x∈Ai(3ra cond de particion)⇒idempot.x∈Ai∧x∈Ai⇒xRx
Transitiva: ∀x,y,z∈A:xRy∧yRz⇒[∃Ai∈P:x∈Ai∧y∈Ai]∧[∃Ak∈P:y∈Ak∧z∈Ak]⇒Ai=Ak(2da prop de particion)⇒∃Ai∈P:x∈Ai∧z∈Ai⇒xRz
Aclaraciones:
NO partir de la tesis a la hora de demostrar las propiedades de una relacion de equivalencia.
En el caso de la propiedad reflexiva, se parte de la hipotesis que un elemento generico que pertenece al conjunto, y luego se llega a la reflexiva
Alguas propiedades de la igualdad que sirven para demostrar las propiedades de una relacion reflexiva son:
Simetria de la igualdad: intercambiar terminos
Transitividad de la igualdad: aplicar "transitividad" en igualaciones
A la hora de armar las clases de equivalencia:
En conjuntos finitos basta con dalre un valor a uno de los elementos y despejar el otro, e ir iterando hasta obtener los valores de todas las clases.
En relaciones de divisibilidad se realiza el mismo procedimiento que en conjuntos finitos.
En relaciones en Reales se toma la expresion y se trata de llegar a formulas que representen las curvas que muestran las clases, en general son dos funciones lineales.
A la hora de armar las clases en este caso nos quedaran dos funciones (en general) la cantidad de clases es infinita, por lo que necesariamente van a estar definidas por las funciones.
En donde se crucen las funciones lineales se formara una unica clase de ese elemento.
Como las clases no se tienen que intersectar entre si por el Teorema Fundamental de las Relaciones de Equivalencia en este tipo de relaciones tendremos que limitar el conjunto de indices, que sera desde donde se crusan hasta el infinito.
Este conjunto de indices es el que pondremos en el conjunto cociente.
En resumen: primero armar las clases, seran dos, una la del elemento donde se intersectan las curvas, el resto son las funciones. Luego se arma el conjunto de indices, que sera desde el elemento donde se intersectan hasta el infinito. Finalmente se arma un conjunto cociente del estilo SR={Cl(x)/x∈[m;∞)} siendo [m;∞) el conjunto de indices.
Unidad 5: Relaciones de Orden
R:A→A es de orden⎩⎨⎧ReflexivaAntisimetricaTransitiva
Las relaciones de orden tambien se llaman de orden amplio
En general estas relaciones son del estilo menor o igual(≤)
Las relaciones de orden se denotan con el simbolo "precede" (⪯)
Si existe una relacion de orden en un conjunto se dice que el conjunto esta ordenado (A;⪯)
Cualquier subconjunto de los naturales relacionado por la division, esta ordenado.
Cualquier conjunto de divisores de un numero n relacionado por la division, esta ordenado.
Diagrama de Hasse
Si se sabe que una relacion es de orden entonces se puede armar un Diagrama de Hasse. Un diagrama de hasse es un digrago de relaciones simplificado, sin bucles ni relaciones transitivas. Solo aristas directas.
Tambien se puede omitir las flechas pero para eso se tiene que hacer de forma vertical, siendo los elementos inferiores los que estan incluidos en en los elementos superiores.
Conjunto Totalmente Ordenado (TTO)
A esta TTO⟺∀x,y∈A:(x⪯y∨y⪯x)
El Diagrama de Hasse de un conjunto tto es una cadena
Aquellos elementos que no esten relacionados (osea que ninguno precede al otro) entonces estos se llaman elementos incomporables. Se denota a//b
Orden Reciproco
Sea (A;⪯)Sea R:A→A/xRy⇔y⪯x
Orden usual del Producto
Sean (A;⪯1) y (B;⪯2)
(x;y)R(z;t)⇔x⪯1z∧y⪯2t
Elementos Notables de un Conjunto Ordenado
Maxiamal
Sea (A;⪯)
m∈A es maximal de A⇔∀x∈A:m⪯x⇒x=m
Si el maximal es unico, se lo llama maximo o ultimo elemento.
Es el que precede a todos los elementos de A.
Minimal
Sea (A;⪯)
m∈A es minimal de A⇔∀x∈A:x⪯m⇒x=m
Si el minimal es unico, se lo llama minimo o primer elemento.
Es el elemento que ningun otro lo precede.
Atomo
Sea (A;⪯) un conjunto ordenado con primer elemento p
m∈A es atomo de A⇔∀x∈A:(x⪯m⇒x=m∨x=p)
Son los que estan inmediatamente despues del primer elemento.
Hay primer elemento cuando el diagrama de hasse converge en un solo elemento.
Conjunto Bien Ordenado
Sea (A;⪯)
A esta Bien Ordenado ⇔todo subconjunto de A tiene 1er elemento
Entonces se deduce que en un conjunto de buen orden no puede haber elementos incomparables.
Buen Orden⇒Orden Total
Cotas Superiores e Inferiores
Sea (A;⪯) un conjunto ordenado y ∅=B⊆A
s∈A es cota superior de B⇔∀x∈B:x⪯s
Sea (A;⪯) un conjunto ordenado y ∅=B⊆A
i∈A es cota inferior de B⇔∀x∈B:i⪯x
El conjunto de cotas superiores se llama Conjunto Mayorante.
El conjunto de cotas inferiores se llama Conjunto Minorante.
La menor de las cotas superiores, recibe el nombre de supremo.
La mayor de las cotas inferiores, recibe el nombre de infimo.
Si el supremo pertenece a B, se llama Maximo de B.
Si el infimo pertenece a B, se llama Minimo de B.
Redes
Sea (A;⪯) un conjunto ordenado.
Es Superior Semirreticulo⟺∀a,b∈A:∃ supremo(a,b)
Sea (A;⪯) un conjunto ordenado.
Es Inferior Semirreticulo⟺∀a,b∈A:∃ infimo(a,b)
Sea (A;⪯) un conjunto ordenado.
(A;⪯) es Red⟺es superior e iferior semirreticulo
Entre todo par de elementos debe existir supremo e infimo.
Entonces para que una relacion sea red, tiene que existir un supremo e infimo para cualquier par de elementos. En relacion a esto entonces, para verificar que esto se cumpla lo mas eficiente seria verificar si hay supremo e infimo entre los elementos incomparables, si es que tienen supremo e infimo en comun entonces la relacion es una red.
Propiedades
Si a⪯b⇒sup(a,b)=byinf(a,b)=a
Si un conjunto ordenado tiene mas de un maximal o mas de un minimal, no puede ser red porque los maximales no tendrian supremo o los minimales no tendrian infimo.
Si un conjunto ordenado tiene solo un maximal y un solo minimal no necesariamente es red porque dos elementos incomparables pueden tener mas de un supremo o mas de un infimo, y esto no cumple con la propiedad de red.
Tabla
Propiedades para las operaciones de supremo e infimo:
Sea (A;⪯) una red. Las operaciones ∨ e ∧ cumplen:
#
Nombre
Propiedad
1
Operacion Cerrada
∀x,y∈A:(x∨y∈A),(x∧y∈A)
2
Asociatividad
∀x,y,z∈A:x∨(y∨z)=(x∨y)∨z∀x,y,z∈A:x∧(y∧z)=(x∧y)∧z
3
Conmutatividad
∀x,y∈A:x∨y=y∨x∀x,y∈A:x∧y=y∧x
4
Idempotencia
∀x∈A:x∨x=x∀x∈A:x∧x=x
5
Absorcion
∀x,y∈A:x∨(x∧y)=x∀x,y∈A:x∧(x∨y)=x
a⪯b⇔a∨b=b⇔a∧b=a
Red Algebraica
Sea un conjunto A=∅,y dos operaciones binarias∗ y ∗′
(A;∗;∗′) es Red Algebraica⟺∗ y ∗′ son ⎩⎨⎧CerradasAsociativasConmutativasIdempotentesy cumple con absorcion
Toda red ordenada se puede expresar como red algebraica. Y toda red Algebraica se puede expresar como red ordenada.
Pasaje
Datos
Requerimientos
Ordenada → Algebraica
La relacion de Orden
Las operaciones ∨ e ∧:a∨b=supremo(a,b)a∧b=infimo(a,b)
Algebraica → Ordenada
Las operaciones binarias ∨ e ∧
La relacion de orden: a⪯b⇔a∧b=aa⪯b⇔a∨b=b
Complemento de un elemento
Sea (A;⪯) una red con primer elemeto 0Ay ultimo elemento 1A
Sea a∈A. Se define complemento de a(a) si{a∧a=0Aa∨a=1A
Red complementada
Una red es complementada⟺cada elemento tiene al menos un complemento
Distributividad
Sea (A;∨;∧) una red, diremos que la red es distributiva sii:
En toda red distributiva el complemento, si existe, es unico.
Toda red finita es distributiva sii no contiene ninguna subred isomorfa a alguna de las siguientes
Es sub red si al suprimir un elemento se concervan los supremos e infimos.
Algebra de Boole
Un algebera de boole es una red distributiva y complementada
Sea (B;∨;∧) diremos que es Algebra de Boole sii:
∨ e ∧ son operaciones binarais cerradas en B.
∨ e ∧ son conmutativas.
∨ e ∧ son distributivas entre si.
∨ e ∧ tienen elementos neutros 0B y 1B respectivamente.
todos los elementos de B tienen complementos.
(Dn) es Algebra de Boole ⇔n es producto de primos distintos.
El cardinal de toda Algebra de Boole es potencia de 2.
Propiedades
En toda Algebra de Boole (B;∨;∧) se cummple:
Todos los elementos 0B y 1B son unicos.
Todo elemento tiene unico complemento.
Todo elemento es idempotente: ∀a∈B:a=aa∧a=a
Los elementos neutros se complementan mutuamente: 1B=0B0B=1B
Todo elemento neutro es involutivo ∀a∈B:a=a
El elemento neutro para ∧ es el 1B y es absorbente para ∨.
El elemento neutro para ∨ es el 0B y es absorbente para ∧.
Se cumple la absorcion: ∀a,b∈B:a∨(a∧b)=a y a∧(a∨b)=a
Se cumple la propiedad asociativa de ∨ e ∧. ∀a,b∈B:a∨(b∨c)=(a∨b)∨c y ∀a,b∈B:a∧(b∧c)=(a∧b)∧c
Leyes de Demorgan: ∀a,b∈B:a∨b=a∧ba∧b=a∨b
Sub Algebra de Boole
Sea (B;⪯) un Algebra de Boole, y ∅=A⊆B,A es subalgebra de B⇔(A,⪯/A) es algebra de boole, y se mantienen los mismos supremos e infimos y elementos neutros.
Homomorfismos de Algebras de Boole:
Sean (A,∨,∧) y (B,∨′,∧′) dos Algebras de Boole, con primeros elementos 0A y 0B respectivamente, y ultimos elementos 1A y 1B
Un homomorfismo de Algebras de Boole es una funcion f:A→B/
f(a)=f(a)
f(a∨b)=f(a)∨′f(b)
f(a∧b)=f(a)∧′f(b)
f(0A)=0B
f(1A)=1B
Si la funcion es bitectiva, se denomina isomorfismo. Para ello es necesario que los conjuntos tengan cardinales iguales. "Dos redes son isomorfas cuando tienen la misma forma aunque distintos elementos".
Toda Algebra de Boole es isomorfa al conjunto de Partes de sus Atomos
Hay tantos isomorfimos como el factorial de la cantidad de atomos.
Funciones Boolenas
Bn→B siendo (B;∨;∧) Algebra de Boole
son las tablas de la verdad.
Circuitos combinacionales
son la representacion de una funcion booleana.
Minitermino
Es un termino en el que intervienen todas las variables o sus complementarios multiplicadas entre si.
Forma Normal Disyuntiva (FND)
Se dice que una funcion booleana esta expresada en forma normal disyuntiva (FND) cuando esta expresada como suma de mini terminos.
Maxitermino
Es un factor en el que intervienen todas las variables o sus complementos Sumadas entre si
Forma Normal Disyuntiva (FNC)
Se dice que una funcion booleana esta expresada en forma normal conjuntiva (FNC) cuando esta expresada como producto de maxi terminos.
Conjuntos Funcionalmente Completos
{AND, OR, NOT}
{AND,NOT}
x+y=x⋅y
{OR, NOT}
x⋅y=x+y
{NAND}
x=x⋅x
x⋅y=x⋅y⋅x⋅y
x+y=x⋅x⋅y⋅y
{NOR}
x=x+x
Relaciones de Recurrencia
f:N→R/∀n∈N:f(n)=an
an sera entonces el termino generico o general.
Recursion
Una definicion es recursiva si hace referencia a si misma.
En las sucesiones se denota una expresion recursiva cuando, a la hora de calcular un an necesitamos conocer un an+1, osea un an anterior o posterior, impidiendo hacer le calculo directo.
Distinto seria el caso en el que para determinar un an basta con reemmplazar el valor de n en la expresion que nos dieron.
Entonces resolver una relacion de recurrencia es expresar nuesrta ecaucion recursiva en una no recursiva.
Expresion Recursiva⟺an=2⋅an−1(a1=4)Expresion NO Recursivaan=2n+1
Clasificacion de Relaciones de Recurrencia
Orden: Es la mayor diferencia entre los subindices de los elementos de la sucesion. Cuantos terminos anteriores hay que conocer para obtener uno particular.
Grado: Es el mayor exponente al que estan elevados los elementos de la sucesion que figuran en la relacion de recurrencia.
Ecaucion Homogenea: Al igual que las ecuaciones algebraicas, las ecuaciones homogeneas son las que no tienen terminos independientes. Es la ecuasion solamente con los an
Coeficientes Constantes: en estas ecuaciones ninguno de los coeficientes de los elementos de la sucesion dependen de n. Por el contrario si alguno depende de n, se dice que la ecuacion tiene coeficientes variables.
Tipos de Relaciones de Recurrencia:
Lineales de orden 1, Homogeneas
Formula:
an=kan−1 siendo k una cte real no nula
Datos:
a0: Es el valor de a para n=0
Forma no recursiva:
an=kan−1⇒an=kna0
Aclaraciones: En estos casos se despeja el an de mayor indice.
Lineales de orden 2, Homogeneas
Formula:
cnan+cn−1an−1+cn−2an−2=0 siendo cn,cn−1,cn−2 ctes reales no nulas
Suponiendo que an=xn, es una solucion valida para la ecuacion:
Reemplazo an por xncnxn+cn−1xn−1+cn−2xn−2Saco factor comun del xn de menor gradoxn−2⋅(cnx2+cn−1x+cn−2)=0Como xn−2 no puede ser 0, igualo a 0 el otro productocnx2+cn−1x+cn−2=0Esto es una ecuacion cuadratica, se la llama caracteristicar1,r2⎩⎨⎧reales y distintas: an=k1r1n+k2r2nreales e iguales: an=k1r1n+k2nr1ncomplejasLuego NOS DEBEN DAR DOS DATOS para obtener el k1 y k2 se plantea un sistemas de ecuaciones con esos dos datos
Lineales de orden 1, No Homogeneas
Formula:
cnan+cn−1an−1=f(n)⇒an=anH+anP
anH: Solucion general de la ecuacion homogenea.
anP: Solucion particular de la ecuacion dada.
Aclaraciones: La solucion del homogeneo es la general, sin tener en cuenta condiciones iniciales. En cambio la solucion particular se plantea como una funcion del mismo tipo que f(n). Si no, se va multiplicando por n sucesivamente hasta hallarla. Por ultimo se plantean condiciones iniciales para despejar las constantes.
f(n)
Solucion Particular Provable
K(cte)
B(cte)
Kn
Bn+C
Kn2
Bn2+Cn+D
Knt
Polinomio completo de grado t
Kan
Ban
ACLARACION: Si aparece un termino como Ktn la solucion particular sera Btn
Si no funka la solucion provable hay que multiplicarla por n hasta que funke, osea se amuenta el grado del polinomio.
estas soluciones provables se reemplazan en la ecuacion y luego esta ecuacion se resuelve como las anteriores.
Se determina una ecuacion Homogenea asociada (sin las cte).
Se obtiene una solucion para la ecuacion homogenea asociada. Esta tendra una constante que despues debemos despejar.
Se elige la solucion particular dependiendo del caso
En la ecuacion original, se reemplaza cada an por la solucion particular (que no conocemos sus ctes).
Despejamos la solucion particular. Obtenemos anP
La ecuacion no recursiva sera an=anH+anP
Ahora si podemos despejar la constante de la solucion homogenea asociada.
Datos:
Nos deben dar un dato inicial.
Lineales de orden 1, No Homogeneas
Formula:
cnan+cn−1an−1+cn−2an−2=f(n)⇒an=anH+anP
Congruencias en Z
Congruencia modulo n
En Z:aRb⇔a≡b(n)⇔n∣a−b
Propiedad:
∀x,y∈Z:Si x∈a(n)∧y∈b(n)⇒x+y∈a+b(n)
∀x,y∈Z:Si x∈a(n)∧y∈b(n)⇒x⋅y∈a⋅b(n)
Funcion de Euler
ϕ(n)=∣{x∈N/x≤n∧mcd(x,n)=1}∣
Osea me devuelve cuantos numeros coprimos hay hasta el numero n
Si p es un numero primo, entonces: ϕ(p)=p−1
Si n es un numero natural y p es numero primo:
ϕ(pn)=pn⋅(1−p1)ϕ(pn)=pn−1(p−1)
Si n,m∈N y mcd(n,m)=1:ϕ(n⋅m)=ϕ(n)⋅ϕ(m)
ϕ(n)=n⋅(1−p11)⋅(1−p21)⋅⋯⋅⋅(1−pr1)
Teorema de Fermat
Si p es primo∧mcd(a,p)=1⇒ap−1≡1(p)
Este teorema se usa para ir simplificando los exponentes para verificar si el resto de una division cae en una clase
Teorema de Euler-Fermat
Si mcd (a,n)=1⇒aϕ(n)≡1(n)
Ecuaciones Lineales de Congruencia
a⋅x≡b(n)
Sea a⋅x≡b(n).Si mcd (a,n)=1 entonces hay solucion.
x=aϕ(n)−1⋅b
a⋅x≡b(n) tiene solucion ⇔mcd(a,n)∣b y la cantidad de soluciones es mcd(a,n)
Esto sirve tambien para simplificar las ecuaciones, se puede dividir termino a termino por la cantidad de soluciones, luego resolver la ecuacion, y finalmente al resultado de la eq simplificada se le suma el modulo simplificado la cantidad de soluciones que hallamos obtenido.
Si:a⋅c≡b⋅c(n)∧mcd(c,n)=1Entonces a≡b(n)
Grupos
OP cerradas
∗ es una operacion binaria cerrada en A sii: ∀x,y∈A:x∗y∈A
Sea un conjunto A=∅∗:A×A→A es operacion cerrada en A ⇔∗ es funcion.
Tambie se llama ley de cierre o lci
Propiedades y elementos notables de una OP cerrada
Sea A=∅ y ∗ es una operacion cerrada definida en A
Asociatividad:
∀a,b,c∈A:(a∗b)∗c=a∗(b∗c)
Conmutativa:
∀a,b∈A:a∗b=b∗a
matricialmente la matriz debe ser simetrica
Elemento neutro:
∃e∈A:∀a∈A:e∗a=a
matricialmente tiene que aparecer el numero correspondiente a la columna o a la fila en toda dicha col o fila. Respeta al otro numero
Elemento simetrico:
a′∈A/a∗a′=a′∗a=e
Elementos Idempotentes:
a∗a=a
matricialmente la diagonal principal tiene que corresponder con la col o fila
Absorvente:
∀a∈A:b∗a=a∗b=b
impone su valor operado con cualquiera
Operaciones combinada
Se tiene que verificar si:
es cerada
es asociativa
conmutativa
tiene neutro, despejar el neutro
tiene simetrico, despejar absovente, puede quedar un elemento simetrico que dependa de otro
idempotente.
tiene absorvente
el neutro siempre es idempotente
Grupos
Si ∗ es op. cerrada ⇒(A;∗) es Grupoide
Si ademas ∗ es asociativa ⇒(A;∗) es Semigrupo
Si ademas ∗ tiene neutro ⇒(A;∗) es Monoide
Si ademas ∗ tiene simetrico ⇒(A;∗) es Grupo
Si ademas ∗ es conmutativa se le agraga el calificativo Abeliano
Propiedades de grupos.
el elemento neutro es unioco
el eutro es su propio simetrico e=e′
propiedad involutiva del simetrico ∀a∈A:(a′)′=a
el simetrico de un elemetno es unico
∀a,b∈A:(a∗b)′=a′∗b′
las ecuaciones lineales tienen solucion unica
el unico elementoidempotente es el elemento neutro
∀a,b,∈A:a′=b⇒b′=a
Dem prop 1: elemento neutro es unico
Suponiendo que hay dos elementos neutros e1 y e2
ϕ es la funcion de incidencia ϕ:A→V
vertices son los nodos (los circulos) y aristas son als lineas que conectan los nodos (en un digrafo son flechas)
Vertices adyacentes: vi es adyacente a vj⇔∃ak∈A tal que ϕ(ak)={vi,vj}. Son aquellos vertices que estan unidos por al menos una arista.
Vertices aislados: vi es aislado ⇔∀vk∈V: Si vi=vk:vi no es adyacente a vk. Son aquellos vertices que no estan unidos por ningun arista.
Aristas Incidentes en un Vertice: ai es Incidente a vk⇔vk∈ϕ(ai). Son las aristas que tienen a un determinado vertice en uno de sus extremos.
Aristas Adyacentes: ai es adyacente a ak⇔∣ϕ(ai)∩ϕ(ak)∣=1. Son las aristas que tienen un vertice en comun.
Aristas Paralelas: ai es paralela a ak⇔ϕ(ai)=ϕ(ak)
Bucles o Lazos: ai es bucle o lazo ⇔∣ϕ(ai)∣=1.
Grafo simple: G es simple sii no tiene aristas paralelas ni bucles.
Representacion matricial de Grafos
Matriz de Adyacencia: es la matriz que muestra entre que vertices hay una arista (es decir son adyacentes)
Es una matriz booleana.
Es una martiz cuadrada de n×n siendo n la cantidad de vertices
Matriz de Incidencia: es la matriz que representa entre que vertices incide una arista.
Es una matriz booleana.
Es una matriz de n×m donde n (las filas) son los vertices y m (las columnas) son las aristas.
Grado o Valencia de un vertice: es la cantidad de aristas que involucran a este vertice.
Los bucles cuentan como doble.
Se denota como g(vi)=n
Si se suma los grados de todos los vertices es igual a al doble de la cantidad de aristas. ∑g(vi)=2∣A∣
Caminos y Ciclos en Grafos
Camino: sucesion de aristas adyacenteas
Ciclo o Circuito: camino cerrado (vertice inicial = vertice final).
Longitud de un camino: cantidad de aristas que lo componen.
Camino Simple: aquel camino en el que todos los vertice son simples.
Caminio y Ciclo de Euler
Camino de Euler: camino que pasa por todas las aristas una sola vez.o
Ciclo de Euler: ciclo que pasa por todas las aristas del grafo.
Un grafo tiene camino euleriano sii es conexo y en todos los vertices tienen grado par, o a lo sumo dos grado impar.
Un grafo tiene ciclo euleriano sii es conexo y todos los vertices tienen grado par
Caminio y Ciclo de Hamilton
Camino de Hamilton: camino simple que pasa por todos los vertices una vez.
Ciclo de Hamilton: ciclo simple que pasa por todos los vertices una vez.
Grafos Regulares
Grafo k-regular: G es k-regular⇔∀v∈V:g(v)=k,k∈N0. Es cuando todos los vertices tienen el mismo grado.
Grafos Completos
Son los grafos cuyos vertices son todos adyacentes entre si.
Todos los vertices tienen grado k-1 siendo k la cantidad de vertices.
Grafo Bipartito
Son los grafos en donde se pueden armar subcoonjuntos de vertices en donde ninguno tiene un arista en comun.
Grafo Bipartito Completo
Es igual que el anterior solo que ahora enrte subconjunto y subconjunto tienen que estar todas las aristas posibles.
Subgrafo
Es el resultado de suprimir uno o mas vertices de un grafo. Al suprimir un vertice se deben suprimir tambien las aristas incidentes.
Grafos Conexos
Es aquel grafo ne el que entre todo par de vertices existe un camino.
Desconexion de grafos
Itsmo o punto de corte: es aquel vertice que al suprimirlo forma un grafo no conexo.
Puente: es aquel arista que al suprimirla forma un grafo no conexo.
conjunto desconectante: Es un conjunto de aristas que alsuprimirlas desconectan el grafo.
Conjunto de Corte: es el conjunto de aristas necesariamente se deben suprimir para formar un grafo no conexo, osea no se suprimen aristas de mas.
Conectividad: es el menor numero de vertices cuya supresion desconecta al grafo.
Grafos Planos
es un grafo cuyas aristas no se superponen.
Un grafo es plano sii no contiene ningun subgrafoisomorfo al K3,3 o al K5
Isomorfismos
Para que dos grafos sean isomorfos sus matrices de incidencia deben ser isomorfas.
Digrafos
Un Digrafo es una terna G=(V;A;δ) Donde:
V : es el conjunto de vertices (V=∅)
A : es el conjunto de aristas dirigidas o arcos.
δ es la funcion de incidencia δ:A→V×V donde V×V es un par ordenado, vi estremo inicial y vj extremo final.
Camino Simple y Camino Elemental en Digrafo
Camino simple: aquel camino en el que todos los vertices osn distintos.
Camino elemental: aquel camino en el que todas las aristas son distitas.
Funcion grado en un digrafo
Grado Positivo: cantidad de arcos o aristas que "entran" al vertice. g+(v)
Grado Negativo: cantidad de arcos o aristas que "salen" del vertice. g−(v)
Grado Total: suma de los grados positivo y negativo. g(v)
Grado Neto: diferencia entre el grado positivo y el negativo. gN(v)
Propiedades
∑g+(vi)=∣A∣
∑g−(vi)=∣A∣
∑g(vi)=2∣A∣
∑gN(vi)=0
Pozo: es un vertice v tal que g−(v)=0. No es extremo inicial de ningun arista, "todas las flechas convergen en el".
Fuente: es un vertice v tal que g+(v)=0. No es extremo final de ningun arista, "todas las flechas salen de el".
Representacion Matricial de Digrafos.
Matriz de Adyacencia: es la matriz que muestra hacia que vertices hay una flecha.
Es una matriz booleana.
Es una martiz cuadrada de n×n siendo n la cantidad de vertices
Matriz de Incidencia: es la matriz que representa entre que vertices incide una arista.
Es una matriz que toma valores de {0,1,-1}.
Es una matriz de n×m donde n (las filas) son los vertices y m (las columnas) son las aristas.
Grafo asociado a un Digrafo
Se simplifica las direccion de las aristas, de haber aristas paralelas si reemplaza por una sola arista
Conexidad en Digrafos
Digrafo Conexo: es todo aquel cuyo grafo asociado sea conexo.
Digrafo fuertemente conexo: es todo aquel en el que exista algun camino entre todo par de vertices.
Camino de Euler y Hamilton en digrafos
Condicion necesaria y suficiente para que exista ciclo de Euler en un digrafo:
∀v∈V:g+(v)=g−(v)
Isomorfismos en Digrafos
es la misma wea que en los grafos solo que hay que tener cuidado con la direccionalidad de las aristas
Arboles
Un arbol es un grafo conexo sin ciclos.
Propiedades
Al agregar una arista entre dos vertices de un arbol, deja de ser arbol
Todas las aristas de un arbol son puentes.
En todo arbol se cumple que ∣V∣=∣A∣+1
Bosques
Un bosque es un grafo no conexo en el cual cada una de sus componentes es un arbol.
En un bosque de k componentes: ∣V∣=∣A∣+k
Arboles Dirigidos
Un digrafo simple es un arbol dirigido si su grafo asociado es un arbol.
Grafo Dirigido con raiz: es un arbol en el cual el grado entrante (positivo) de cada vertice es igual a 1, salvo un unico verticve con grado positivo igual a cero llamado raiz.
Definiciones:
Un vertice v de un arbol se dice que es hoja cuando g(v)=1
Los vertices interinos son todos aquellos que no son la raiz ni las hojas.
Se llama rama a todo camino que va desde la raiz a alguna hoja.
v es antecesor de w⟺ existe un unico camino simple de v a w
w es sucesor de v en el caso anterior.
v es padre de w⟺ existe una arista de v a w
w es hijo de v en el caso anterior.
v y w son hermanos si tienen el mismo padre.
Otras Definiciones:
Nivel de un vertice: El nivel de la raiz es cero: n(r)=0 Cada vertice tiene un nivel mas que su padre: si p es padre de v→n(v)=n(p)+1
Altura de un arbol: Es el mayor nivel alcanzado por las hojas.
Arbol balanceado: Si todas las hojas estan en el nivel h o h−1 (siendo h la altura del arbol).
Arbol n-ario
Arbol n-ario: Un arbol con raiz es n-ario ⇔∀v∈V:g−(v)≤n. Cada vertice puede tener a lo sumo n hijos.
Arbol n-ario regular: Si todos ls vertices tienen la misma cantidad de hijos , salvo las hojas que no tienen hijos.
Arbol n-ario regular completo: Si ademas de ser n-ario regular, todas las hojas se hayan al mismo nivel.
Recorridos de Arboles
Subarbol: Sea G=(V;A;δ) un arbol con raiz r. Sea v∈V, se llama subarbol con raiz v, y se indica T(v), al arbol que consta de v, todos sus descendientes y las aritas entre ellos.
Rrcorrer un arbol es una forma de nombrar todos los vertices segun un orden determinado.
Pre-orden: Raiz - subarbol izq - subarbol der
In-orden: subarbol izq - Raiz - subarbol der
Post-orden: subarbol izq - subarbol der - Raiz
se puede recorrer como el pre-orden solo que en sentido opuesto, luego al final invertir la secuencia.
Representacion de expresiones algebraicas
se puede representar una suma como un arbol, y asi con el resto de operaciones.
Notacion polaca: Pre-orden
Notacion usual o infija: In-orden
Notacion polaca inversa: Post-orden
Lenguajes
Alfabeto
Conjunto finito no vacio, sin elementos que se obtengan por yuxtaposicion (poner dos letras consecutivas).
Se simboliza con la letra V o con ∑
Palabra: secuencia finita de letras.
Palabra nula: esta formada por 0 letras se simboliza con λ.
Longitud: cantidad de letras que la forman.
Clausura de Kleene de un Alfabeto
V∗=V0∪V1∪V2∪⋯VnVi: conjunto de palabras de longitud i formadas con las letras del alfabeto V
Entonces V∗ sera el conjunto de todas las palabras, de cualquier longitud, que se puede escribir con letras del alfabeto.
∣Vn∣=n∣V∣
Concatenacion de palabras.
Literalmente concatenar palabras, se simboliza como w3=w1⋅w2 siendo w1,w2,w3 palabras.
long(w1⋅w2)=long(w1)+long(w2)
w1⋅(w2⋅w3)=(w1⋅w2)⋅w3
Inversion o trasposicion: es la palabra que se obtiene al escribir dicha palabra de "atras hacia adelante" se simboliza wR
wRR=w
(w1⋅w2)R=w2R⋅w1R
λR=λ
long(wR)=long(w)
Palindromo
Sea w una palabra ∈V∗,w es palindromo ⟺w=wR
Potencai de una palabra
Sea w∈V∗ se define:
⎩⎨⎧w0=λw1=wwn=w⋅wn−1con n∈N0
long(wn)=n⋅long(w)
Lenguaje
Sea L un conjunto y V un alfabeto. L es un lenguaje ⟺L⊆V∗
Los lenguajes pueden ser finitos o infinitos
Como L⊆V∗ entonces L∈P(V∗)
L al ser un conjunto se le pueden aplicar operaciones de conjuntos.
L puede no tener ningun elemento.
Lenguajes especiales:
L={λ}=Λ se llama lenguaje nulo.
L=∅ se llama lenguaje vacio (no tiene palabras).
Concatencaion de Lenguajes
L=L1⋅L2={xy/x∈L1∧y∈L2}
∣L1⋅L2∣≤∣L1∣⋅∣L2∣
(P(V∗);∙) semigrupo con neutro L=Λ
L1⋅L2=L2⋅L1
L=∅ es elemento absorbente de la concatenacion.
Si L1⊂L2 y L3⊂L4 entonces L1⋅L3⊂L2⋅L4
Lenguaje inverso reflejo o traspuesto:
LR={wR/w∈L}, son todas las palabras del lenguaje reflejadas.
Potencia de un Lenguaje
⎩⎨⎧L0={λ}L1=LLn=L⋅Ln−1con n∈N0
Clausura de Kleene de un Lenguaje
L∗=n=0⋃∞Ln=L0∪L1∪L2∪⋯∪Ln∪⋯
Λ∗=Λ
∅∗=Λ
∀L:λ∈L∗
Clausura Positiva de un Lenguaje
L+=n=1⋃∞Ln=L1∪L2∪⋯∪Ln∪⋯
Λ+=λ
∅+=∅
Complemento de un Lenguaje
L=V∗−L
Gramatica
G=(Vn;Vt;P;S)Vn: Vocabulario o alfabeto de no terminales.Vt: Vocabulario o alfabeto de Terminales.P: Producciones.S: Simbolo o variable inicial.
Vn y Vt son conjuntos finitos
Vn∩Vt=∅
P es finito y P⊂(V+−Vt∗)×V∗ sinedo V=Vn∪Vt
S pertenece a Vn
Aclaraciones:
las no terminales son las variables que generan las palabras
terminales son las letras con las que se forman las palabras
P
Gramaticas equivalentes
Son las que generan el mismo lenguaje.
Tipos de Gramaticas (Jerarquia de Chomsky)
Tipo
Nombre
Producciones
0
Irrestricta
Cualquier forma
1
Sensible al Contexto
aXb→aYb donde a,b,Y∈V∗X∈Vn
2
Independiente del Contexto
X→Y donde X∈Vn
3
Regular
X→Y donde X∈VnY puede ser Vt,t o λ (derecha) Y puede ser tV,t o λ (izquierda)
Un lenguaje puede estar generado por distintas gramaticas de distinto tipo para un mismo lenguaje, pero el tipo del lengua sera el de la gramatica de mayor tipo.
digraph g{
rankdir=LR;
g [label=gramatica, shape= rectangle]
l [label=lenguaje, shape= rectangle]
g -> l [label=Unico]
l -> g [label=Muchos]
}
Expresiones Regulares
Una ER es una secuencia de elementos que verifica:+
λ es ER
a∈V entocnes a es ER
Si X,Y son ER entonces X⋅Y es ER
Si X,Y son ER entonces X+Y es ER
Si X es ER entonces X∗ es ER
Automatas Finitos
Maquinas de estados finitos
Lenguaje Tipo
Maquina que lo Reconoce
0
Mauina de Turing
1
Automata linealmente Acotado
2
Automata de Pila (Push Down)
3
Automata Finito
Automata Finito
A=(Q,V,λ,q0,F)Q: Conjunto finito de estados
V: vocabulario o alfabeto de enrtada
λ:Q×V→Q. Funcion de transision
q0: Estado Inicial
F: Conjunto de estados finales F=∅ y F⊂Q
Tabla de Transicion
x
y
q0
q0,q1
q1
q1
q2
q2
q1
la primer columna son los estados posibles del automata
la primer fila son las letras del alfabeto
lo que hay en cada celda es a que estado se dirige si se elige una letra.
Clasificacion de los Automatas Finitos
Automatasfinitos{A.F.D: DeterministicoA.F.N: No Deterministico
AFD: no tiene transisciones por λ, cumple con ley de unicidad. Osea, no usa el caracter λ para alguna de las aristas, y no presenta dos posibles caminos para el mismo caracter.